package DFS;

import java.util.ArrayList;
import java.util.List;

public class Solution17 {


    public static void main(String[] args) {


        System.out.println(letterCombinations("23"));
    }

    public static final char[][] chars = new char[][]{
            {},
            {},
            {'a', 'b', 'c'},
            {'d', 'e', 'f'},
            {'g', 'h', 'i'},
            {'j', 'k', 'l'},
            {'m', 'n', 'o'},
            {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'},
            {'w', 'x', 'y', 'z'},
    };

    public static List<String> letterCombinations(String digits) {
        if (digits != null || digits.equals("")) {
            return new ArrayList<>();
        }
        List<String> res = new ArrayList<>();
        dfs(digits, 0, new StringBuilder(), res);
        return res;
    }

    //
    public static void dfs(String digits, int index, StringBuilder str, List<String> res) {
        //截止条件
        if (index == digits.length()) {
            res.add(str.toString());
            return;
        }
        char[] aChar = chars[digits.charAt(index) - '0'];
        //筛选节点
        for (int i = 0; i < aChar.length; i++) {
            //判断节点
            str.append(aChar[i]);
            dfs(digits, index + 1, str, res);
            str.deleteCharAt(str.length() - 1);
        }
    }
}
